/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2016年5月9日上午10:09:04
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.link;

import com.xuwei.base.link.DLNode;
import com.xuwei.base.link.Iterator;
import com.xuwei.base.link.Node;
import com.xuwei.ext.exception.InvalidNodeException;
import com.xuwei.ext.exception.OutOfBoundaryException;

/**
 * 基于双向链表实现的链接表
 * @author David
 * @since 2016年5月9日 上午10:09:04
 * @version 
 * @since JDK 1.6
 */
public class LinkedListDLNode implements LinkedList {
	private int size;
	private DLNode head;//头结点
	private DLNode tail;//尾结点
	public LinkedListDLNode(){
		size = 0;
		head = new DLNode();//构建只有头尾结点的链表
		tail = new DLNode();
		head.setRear(tail);
		tail.setPrior(head);
	}
	
	//辅助方法，判断结点p是否合法，如合法转换为DLNode
	protected DLNode checkPosition(Node p)throws InvalidNodeException{
		if(p==null){
			throw new InvalidNodeException("错误：p为空。");
		}
		if(p==head){
			throw new InvalidNodeException("错误：p指向头结点，非法。");
		}
		if(p==tail){
			throw new InvalidNodeException("错误：p指向尾结点，非法。");
		}
		DLNode node = (DLNode)p;
		return node;
	}
	
	//查询链接表当前的规模
	@Override
	public int getSize() {
		return size;
	}

	//返回第一个结点
	@Override
	public boolean isEmpty() {
		return size==0;
	}

	//返回第一个结点
	@Override
	public Node first() throws OutOfBoundaryException {
		if(isEmpty()){
			throw new OutOfBoundaryException("错误：链接表为空。");
		}
		return head.getRear();
	}

	//返回最后一个结点
	@Override
	public Node last() throws OutOfBoundaryException {
		if(isEmpty()){
			throw new OutOfBoundaryException("错误：链接表为空。");
		}
		return tail.getPrior();
	}

	//返回p之后的结点
	@Override
	public Node getNext(Node p)
			throws InvalidNodeException, OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getRear();
		if(node==tail){
			throw new OutOfBoundaryException("错误：已经是链接表尾端。");
		}
		return node;
	}

	//返回p之前的结点
	@Override
	public Node getPre(Node p)
			throws InvalidNodeException, OutOfBoundaryException {
		DLNode node = checkPosition(p);
		node = node.getPrior();
		if(node==head){
			throw new OutOfBoundaryException("错误：已经是链接表前端。");
		}
		return node;
	}

	//将e作为第一个元素插入链接表
	@Override
	public Node insertFist(Object e) {
		DLNode node = new DLNode(e, head, head.getRear());
		head.getRear().setPrior(node);
		head.setRear(node);
		size++;
		return node;
	}

	//将e作为最后一个元素插入列表，并返回e所在结点
	@Override
	public Node insertLast(Object e) {
		DLNode node = new DLNode(e,tail.getPrior(),tail);
		tail.getPrior().setRear(node);
		tail.setPrior(node);
		size++;
		return node;
	}

	//将e插入至p之后的位置，并返回e所在结点
	@Override
	public Node insertAfter(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e, node, node.getRear());
		node.getRear().setPrior(newNode);
		node.setRear(newNode);
		size++;
		return newNode;
	}

	//将e插入至p之前的位置，并返回e所在结点
	@Override
	public Node insertBefore(Node p, Object e) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		DLNode newNode = new DLNode(e, node.getPrior(), node);
		node.getPrior().setRear(newNode);
		node.setPrior(newNode);
		size++;
		return newNode;
	}

	//删除给定位置处的元素，并返回之
	@Override
	public Object remove(Node p) throws InvalidNodeException {
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.getPrior().setRear(node.getRear());
		node.getRear().setPrior(node.getPrior());
		size--;
		return obj;
	}

	//删除首元素，并返回之
	@Override
	public Object removeFirst() throws OutOfBoundaryException {
		return remove(head.getRear());
	}

	//删除末元素，并返回之
	@Override
	public Object removeLast() throws OutOfBoundaryException {
		return remove(tail.getPrior());
	}

	@Override
	public Iterator elements() {
		return new LinkedListIterator(this);
	}
	
	//将处于给定位置的元素替换为新元素，并返回被替换的元素
	public Object replace(Node p, Object e)throws InvalidNodeException{
		DLNode node = checkPosition(p);
		Object obj = node.getData();
		node.setData(e);
		return obj;
	}

}
